package
{
	public class BoyerMoore
	{
		private var badChars:Array = null;
		private var suffixs:Array = null;
		private var goodSuffixs:Array = null;
		
		public function find(str:String, pattern:String):void
		{
			this.createBadChars(pattern);
			this.createGoodsSuffixs(pattern);
			var j:uint = 0;
			var n:uint = str.length;
			var m:uint = pattern.length;
		    while(j <= n - m)
		    {
			        for(var i:int = m - 1; i >= 0 && pattern.charCodeAt(i) == str.charCodeAt(i + j); i--);
			        if(i < 0)
			        {
				            trace("Find it, the position is ", j);
				            j += goodSuffixs[0];
			        }
			        else
			        {
				            j += Math.max(this.badCharsOffset(str.charAt(i+j),pattern)- m + 1 + i, goodSuffixs[i]);
			        }
		    }

			return ;
		}
		
		/** 创建欢坏字符索引数组*/
		private function createBadChars(pattern:String):void
		{
			badChars = [];
			var len:uint = pattern.length;
			var i:int = 0;
			for(i = 0; i < pattern.length; i++){
				badChars[pattern.charCodeAt(i)] = len - i;
			}
		}
		
		private function createSuffixs(pattern:String):void
		{
			var len:uint = pattern.length;
			var subLen:int = 0;
			var count:uint = 0;
			suffixs = [];
			suffixs[len - 1] = len;
			for(var i:int = len - 2; i > 0; i--){
				subLen = i;
				count = 0;
				for(var j:int = 0; j < subLen; j++){
					if(pattern.charAt(len - 1 - count) != pattern.charAt(subLen - count)){
						break;
					}
					count++;
				}
				suffixs[i] = count;
			}
		}
		
		private function createGoodsSuffixs(pattern:String):void
		{
			createSuffixs(pattern);
			var len:uint = pattern.length;
			goodSuffixs = [];
			var i:int = 0;
			for(i = 0; i < len; i++){
				goodSuffixs[i] = len;
			}
			var j:int = 0;
			for(i = 0; i < len - 1; i++){
				if(suffixs[i] == i + 1){
					for(j = i + 1;j < len - 1 - i; j++){
						goodSuffixs[j] = len - 1 - i;
					}
				}
			}
			
			for(i = 0; i < len - 2; i++){
				goodSuffixs[len - 1 - suffixs[i]] = len - 1 - i;
			}
		}
		
		private function badCharsOffset(str:String, pattern:String):int
		{
			var ret:int = pattern.length;
			var index:int = str.charCodeAt();
			if(badChars.hasOwnProperty(index)){
				ret = badChars[index];
			}
			return ret;
		}
	}
}